#include <iostream>
#include <vector>
#include <algorithm>
#define INT_MAX 10000
using namespace std;

/*
求一般有向图的单源最短路径
坑：有环图的循环依赖问题
与有向无环图计算单源最短路径的区别在于：
加入一个变量描述决策步数，
n为一般有向图的顶点的个数，则从s到t顶点的最短路径不超过 n-1
定义子问题为dp[v][k]：计算从顶点s到顶点v，最多包含k条边的最短路径为dp[v][k]
本题只考虑正权重环，不考虑负权重环的情况，（负权重环存在权重依赖问题）
显然，正权重环是不可能出现在最短路径上的。
*/

int dg_short_path(vector<vector<int> > &dag, int n){
    //n为顶点的个数,最多经过的边数 k, 1 <= k <= n
    int dp[n][n];
    fill(dp[0], dp[0] + n*n, INT_MAX);
    //源点无论最多经过多少条边到自己最短路径都是0
    for (int i = 0; i < n; i++) 
        dp[0][i] = 0;
    
    for (int i = 1; i < n; i++)
        dp[i][0] = dag[0][i];


    for (int i = 2; i <= n; i++) { //外循环遍历k边数, k = i
        for (int j = 1; j < n; j++) {
            for (int l = 0; l < j; l++) { //遍历l的作用是循环比较取得最小值min
                //需要计算的是dp[j][i-1]
                if (dp[l][i-2] + dag[l][j] < dp[j][i-1]) {
                    dp[j][i-1] = dp[l][i-2] + dag[l][j];
                }
            }
            if (dp[j][i-2] < dp[j][i-1])
                dp[j][i-1] = dp[j][i-2];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    return 0;

}

int main(){
    // 有 6 个顶点
    int n = 6;
    // 表示拓扑排序序列
    vector<int> point1 = {0, 3, 5, INT_MAX, INT_MAX, INT_MAX};
    vector<int> point2 = {INT_MAX, 0, -2, -2, INT_MAX, INT_MAX};
    vector<int> point3 = {INT_MAX, 3, 0, INT_MAX, -1, INT_MAX};
    vector<int> point4 = {INT_MAX, INT_MAX, 1, 0, INT_MAX, 7};
    vector<int> point5 = {INT_MAX, 4, INT_MAX, INT_MAX, 0, 9};
    vector<int> point6 = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0};
    vector<vector<int> > dag;
    dag.push_back(point1);
    dag.push_back(point2);
    dag.push_back(point3);
    dag.push_back(point4);
    dag.push_back(point5);
    dag.push_back(point6);
    cout << dg_short_path(dag, n) << endl;
    return 0;
}